735D - Taxes - CodeForces Solution

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define boost ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define fill(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define pf push_front
//#define endl '\n'
#define fi first
#define se second
#define sz size()
#define mp make_pair
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
const ll INF = (ll)1e18 + 10;
const int N = 1e6;
const int M = N + 5;
const ld eps = 1e-12;
const ld pi = acos(-1);
const int dx[] = {0,0,-1,1,1,1,-1,-1},dy[] = {-1,1,0,0,1,-1,1,-1};
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
bool isprime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
void solve(){
	int n;
	cin>>n;
	if(isprime(n)){
		cout<<1;
	}
	else if(n%2==0||isprime(n-2)){
		cout<<2;
	}
	else{
		cout<<3;
	}
}
int main() {
    //boost;
    srand(time(0));
    //freopen("", "r", stdin);
    //freopen("","w",stdout);
    int ttt;
 	ttt=1;
    while(ttt--){
    	solve();
    }
    return 0;
}